package greedy;

/**
 * 跳跃游戏II
 * 使用最少的跳跃次数到达数组的最后一个位置。
 */
public class JumpGameII {

    public static void main(String[] args) {
        int[] paces = new int[] {2,3,1,1,4};
        // 跳跃次数
        int count = 0;
        // 当前能够到达的最远位置
        int maxPos = 0;
        // 当前步数的结束位置
        int endIndex = 0;

        for (int i = 0; i < paces.length-1; i++) {
            // 获取最远位置
            maxPos = Math.max(maxPos,i+paces[i]);
            // 当前范围遍历结束
            if (i == endIndex) {
                // 更新结束步数
                endIndex = maxPos;
                count++;
            }
        }
        System.out.println(count);
    }
}
